package xyz.vopen.leetcode.q354;

import java.util.Arrays;
import java.util.Comparator;

/**
 * {@link ElveXu}
 *
 * @author <a href="mailto:iskp.me@gmail.com">Elve.Xu</a>
 * @version ${project.version} - 2020-05-04.
 */
public class ElveXu {

  public static void main(String[] args) {

  }

  public int maxEnvelopes(int[][] envelopes) {

    Arrays.sort(envelopes, Comparator.comparingInt(a -> a[0]));
    int[] dp = new int[envelopes.length];
    Arrays.fill(dp, 1);
    int max = 0;
    for (int i = 0; i < dp.length; ++i) {
      for (int j = 0; j < i; ++j) {
        if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      max = Math.max(max, dp[i]);
    }
    return max;
  }
}
